package util;


import java.util.LinkedList;
import java.util.Queue;

/**
 * 模仿 LeetCode 格式，定义 二叉树 的数据结构
 *
 * @author Liu Huan
 */

public class TreeNode {
	
	public int val;
	public TreeNode left;
	public TreeNode right;
	
	public TreeNode(int x) {
		val = x;
	}
	
	public TreeNode(int x, TreeNode left, TreeNode right) {
		this.val = x;
		this.left = left;
		this.right = right;
	}
	
	/**
	 * 由 数组 生成 二叉树
	 * @param array Integer[]
	 * @return      TreeNode
	 */
	public static TreeNode getTreeFromArray(Integer[] array) {
		if (array.length == 0) {
			return null;
		}
		TreeNode root = new TreeNode(array[0]);
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		boolean isLeft = true;
		for (int i = 1; i < array.length; i++) {
			TreeNode node = queue.peek();
			if (isLeft) {
				if (array[i] != null) {
					node.left = new TreeNode(array[i]);
					queue.offer(node.left);
				}
				isLeft = false;
			} else {
				if (array[i] != null) {
					node.right = new TreeNode(array[i]);
					queue.offer(node.right);
				}
				queue.poll();
				isLeft = true;
			}
		}
		return root;
	}
	
	/**
	 * 层级打印 二叉树，不打印 null 值
	 * @param root
	 */
	public static void printTreeNotNull(TreeNode root) {
		if (root == null) return;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		
		System.out.printf("{ ");
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			System.out.printf(node.val + ", ");
			if (node.left != null) queue.offer(node.left);
			if (node.right != null) queue.offer(node.right);
		}
		System.out.printf("}");
		System.out.println();
	}
	
	/**
	 * 层级打印 二叉树，打印 null 值
	 * @param root
	 */
	public static void printTree(TreeNode root) {
		if (root == null) return;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		
		int height = getMaxHeight(root);
		int level = 0;
		System.out.printf("{ ");
		while (!queue.isEmpty() && level++ < height) {
			int n = queue.size();
			for (int i = 0; i < n; i++) {
				TreeNode node = queue.poll();
				if (node == null) {
					System.out.printf("null," + " ");
				} else {
					if (level == height && i == n-1) {
						System.out.printf(node.val + " ");
					} else {
						System.out.printf(node.val + ", ");
					}
				}
				if (node == null) {
					queue.offer(null);
					queue.offer(null);
				} else if (node.left == null && node.right != null){
					queue.offer(null);
					queue.offer(node.right);
				} else if (node.left != null && node.right == null){
					queue.offer(node.left);
					queue.offer(null);
				} else {
					queue.offer(node.left);
					queue.offer(node.right);
				}
			}
		}
		System.out.printf("}");
		System.out.println();
	}
	
	private static int getMaxHeight(TreeNode root) {
		if (root == null) return 0;
		return Math.max(getMaxHeight(root.left), getMaxHeight(root.right)) + 1;
	}
	
}
